import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SolutionInterview8_7 {
    public String[] permutation(String S) {
        List<String> list=new ArrayList<>();
        boolean[] used=new boolean[S.length()];
        dfs(S,used,0,list,new StringBuilder());
        String[] ans=new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i]=list.get(i);
        }
        return ans;
    }

    private void dfs(String s, boolean[] used, int k, List<String> list, StringBuilder stringBuilder) {
        if (k==s.length()){
            list.add(stringBuilder.toString());
            return;
        }
        for (int i=0;i<s.length();i++){
            if (!used[i]){
                used[i]=true;
                stringBuilder.append(s.charAt(i));
                dfs(s,used,k+1,list,stringBuilder);
                stringBuilder.deleteCharAt(stringBuilder.length()-1);
                used[i]=false;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new SolutionInterview8_7().permutation("qwe")));
    }
}
